This invention relates to the protection of communication networks against span failures.
The inventor Wayne D. Grover has previously proposed a method for the automated synthesis of transport network designs based on multiple SONET self-healing rings. [Grover et al, Optimized Design of ring-based Survivable Networks, Can. J. Elect. and Comp. Eng., vol. 20, No. 3, 1995] A heuristic procedure was based on insights about the trade-off between capacity efficiency and traffic capture efficiency of ring sets to find a minimum-cost composite design. The method was called RingBuilder(trademark) Version 1. In the method, demands are first mapped onto the spans of a network via shortest-path routing, with a load leveling criterion if multiple equal-length shortest routes are present. This produces a network graph. Next, all distinct simple cycles in the network graph are identified. Then, each cycle is evaluated according to a metric to find a cycle that maximizes the metric. The proposed metric evaluated capacity efficiency. After a maximizing cycle is found, all the working capacities on spans in the maximizing cycle are set to zero for subsequent iterations of the method steps. The remaining distinct simple cycles are then evaluated according to the metric, and maximizing cycles identified at each iteration, until all spans in the network are covered by a bi-directional line-switched ring.
Some limitations of RingBuilder Version 1 are as follows. Version 1 is only suitable for designing networks that are based entirely on a single size and type of ring technology. Version 1 does not directly optimize the cost of the rings it is choosing. It pursues a weighted trade-off between capture and balance efficiency over a range of compromise weightings. Total network design cost is reported at design termination. Separate cost evaluation is required to find the minimum cost design amongst the designs generated. The process of generating complete designs at each xe2x80x98alphaxe2x80x99 (weighting factor) value is very time consuming. Largely because of the computational complexity of sweeping the value of alpha, Version 1 cannot afford to apply any anti-greediness methods or other forms of search to explore the design space around each sweep-generated design. Version 1 is relatively susceptible to missing very good designs because only one synthesis sequence is invested at each alpha value. If used to generate pure balance-optimized designs, Version 1 often does not escape the use of small individually efficient rings. This has the undesirable side effect that more rings than really necessary are often used in the final design. Because of this Version 1 sometimes fails to discover good designs which humans can find by careful inspection and proposal of rings. These designs often involve manually selected span eliminations, which is the deliberate disuse of a topologically existing span, because it can be more cost effective not to use the span at all in the design.
Bi-directional line-switched rings (BLSR) and uni-directional path-switched rings (UPSR) are now in common use for survivable transport networking. (Nortel Networks, xe2x80x9cIntroduction to SONET Networking,xe2x80x9d SONET 101 Tutorial Handbook, Oct. 30, 1996) These protection structures offer fast restoration speeds (typically under 150 msec) and, though not as capacity efficient as mesh networks, each ring is individually simple to operate. Ring networks can also be more economical than mesh in metro applications due to their lower nodal equipment costs. (T. Flanagan, xe2x80x9cFiber Network Survivability,xe2x80x9d IEEE Comm. Mag., pp. 46-53, June 1990)
However, the design of multi-ring networks is an exceptionally complex combinatorial optimization problem. In recent years, a number of approximate design methods have been proposed for the multiple-ring design problem which approach the design as a form of min-cost graph-covering problem. W. D. Grover, J. B. Slevinsky, M. H. MacGregor, xe2x80x9cOptimized Design of Ring-Based Survivable Networksxe2x80x9d, Can. J. Elect and Comp. Eng., Vol. 20, No.3, 1995. O. J. Wasem, T-H Wu and R. H. Cardwell, xe2x80x9cSurvivable SONET Networks-Design Methodology,xe2x80x9d IEEE J. on Select Areas Comm., vol. 12, no. 1, pp. 205-212, January 1994. B. Doshi and P. Harshavardhana, xe2x80x9cBroadband Network Infrastructure of the Future: Roles of Network Design Tools in Technology Deployment Strategies,xe2x80x9d IEEE Comm. Mag., vol. 39, pp.60-71, May 1998. L. M. Gardner, I. H. Sudborough and I. G. Tollis, xe2x80x9cNet Solver: A Software Tool for the Design of Survivable Networks,xe2x80x9d IEEE GLOBECOM 1995, vol. 1, pp. 39-44, November 1995).
Some schemes take a capacitated coverage view (the ring capacities placed must be adequate to carry all demand crossing the underlying span), or an uncapacitated, purely logical coverage viewpoint (at least one ring covers every span). (L. M. Gardner, M. Heydari, J. Shah, I. H. Sudborough, I. G. TIEEE GLOBECOM 1994, vol. 3, pp. 1862-1866, 1994.)
Generally, the capacity requirements of each span are determined by routing demands over the shortest path from end-to-end. Intuitively, this can lead to coverage solutions with one or more very low-utilization rings; rings that were placed, in essence, just due to the strict coverage requirement, but serve little demand. To illustrate, consider the simple graph and demand matrix in FIG. 1(a) where the capacity required on each span has been determined by shortest path routing over the native graph. If we assume OC-12 4-fibre BLSRs, a minimum of two rings is required in a xe2x80x98coveragexe2x80x99 design. Moreover both of these rings are forced to cover span B-D. And together they have only 2/24th capacity utilization on that span.
In this case it is fairly apparent by inspection that xe2x80x9celiminatingxe2x80x9d span B-D would force the B-D demand flow to take another route or routes (with demand bundle splitting) and, as constructed in FIG. 11(b) result in a single perfectly filled OC-12 ring to cover the network graph. Note that the capacity utilization of the ring increases at the same time as fewer rings are used due to eliminating span B-D. The capacity and capture efficiency are both improved
The example is a simple one. More generally the challenge is to identify those spans of a graph which, for a given demand pattern and ring modularities, will have desirable effects as above, if eliminated. If the wrong span is eliminated, it can backfire: total (inter-ring) routing costs increase due to excessive detouring from the shortest path and ring counts can increase due to exceeding a modularity threshold. It is known that experienced manual planners, with some trial and error, can fairly effectively visualize these opportunities in complex real-sized problems. To our knowledge, however, our work is the first attempt at a systematic algorithmic approach to span elimination.
The present invention provides an improvement over RingBuilder(trademark) Version 1 for optimized design of multiple ring networks, such as SONET and WDM networks. For example, multi-technology designs are possible, unlike in RingBuilder(trademark) Version 1. Other advantages of the present invention include: Ring choices in each iteration are based directly on cost assessment, and not on the intermediate measures of balance and capture efficiency. The total cost of the design is known immediately at the end of the run. A minimum cost final design can be determined without sweeping. Anti-greediness tactics are employed, exploring the design space in the region of the basic synthesis sequence to a significant and user-specifiable extent.
Aspects of the invention include:
iterative ring selection via transport utility (or xe2x80x9cbang for the buckxe2x80x9d),
aggregating routing,
statistically xe2x80x9cditheredxe2x80x9d ring choice selection,
random or systematic cycle-set masking on a per iteration basis,
progressive expansion of cycle set scope as the design evolves to completion,
wide xe2x80x98horizontalxe2x80x99 searches of partial designs followed by progressive design depth search to completion,
systematic use of aggregation pressure for discovery of cost-effective span additions or eliminations,
xe2x80x98bundledxe2x80x99 demand processing has been implemented, which ensures that an entire demand is treated as a single unit for processing by RingBuilder, increasing performance and simplifying network implementation,
1:1 system substitution post-processor which searches a complete ADM-based ring design and searches for opportunities replace ADM-based systems with simpler diversely routed linear systems,
and
Ring loading methods: 1) balance-biased demand ordering, 2) capture-biased demand ordering, and 3) intra-ring demand alternate routing ring loader which allows limited re-routing of demands within a ring in order to enhance system utilization.
Therefore, according to an aspect of the invention, there is provided a method of constructing a telecommunications network, in which the network is formed of plural nodes connected by plural spans, each node having a nodal switching device for making connections between adjacent spans meeting at the node, the method comprising the steps of:
a) selecting a set of candidate rings, each candidate ring being formed of nodes connected by spans, the candidate rings each being capable of serving a number of demands and having a ring construction cost C;
b) assessing the total transport utility U of each candidate ring, wherein the total transport utility is a measure of at least the number of demands served by the respective candidate ring;
c) assessing the construction cost of each candidate ring;
d) calculating a ratio formed of U/C for each candidate ring;
e) choosing, from the set of candidate rings, a best set of candidate rings, wherein candidate rings in the best set of candidate rings have a higher ratio of U/C than candidate rings not in the best set; the best set of candidate rings being capable of covering the network; and
f) forming rings in the network that are selected from the best set of candidate simple rings.
According to a further aspect of the invention, there is provided A method of connecting a telecommunications network, in which the network is formed of plural nodes connected by plural spans, each node having a nodal switching device for making connections between adjacent spans meeting at the node, the method comprising the steps of:
a) selecting a set of candidate rings, each candidate ring being formed of nodes connected by spans;
b) assigning an amount of demand to each candidate ring;
c) ordering the candidate rings according to a rule that considers the cost of implementing the candidate rings in the network in relation to the level of demand coverage provided by the candidate rings;
d) selecting a set of best rings from the candidate rings, wherein the best rings are ordered higher than rings not in the best set;
e) setting the demand in the best rings to zero;
f) re-ordering the remaining candidate rings not in the best set according to a rule that considers the cost of implementing the candidate rings in the network in relation to the level of demand coverage provided by the remaining candidate rings; and
g) forming rings in the network that are selected from the best set of candidate rings and rings in the remaining candidate rings that are ordered higher than other rings in the remaining candidate rings.
According to a further aspect of the invention, there is provided A method for selecting a ring for implementation in a communications network, the communications network comprising plural spans connected by nodes for data transmission, the method comprising the steps of:
selecting a set of cycles, a cycle being a set of nodes and their interconnecting spans forming a closed path for travel once over each span and node in the cycle;
for each cycle in the set;
identifying the demands with demand route segments in the cycle, a demand being an amount of data required to be transmitted between a source node and a destination node, a demand route being a set of connected spans and nodes over which the demand is transmitted and a demand route segment being any number of spans and nodes in the demand route;
calculating the cost of carrying the demands on the cycle, and a cost and performance value for the cycle; and
selecting one cycle as a ring based on the cost and performance value.
According to a further aspect of the invention, there is provided A method of selecting demand routes in a communications network, the communications network being plural spans connected by nodes for carrying data, a demand route being a set of connected spans and nodes over which data is transmitted between a source node and a destination node, the method comprising the steps of:
Identifying a set of spans such that each span in the set is essential for bi-connectivity and route maximum node number limitations; and
for each demand:
calculating a cost value for carrying the demand for each span in a possible route; and
selecting the demand route according to the cost values for spans calculated in i).
According to a further aspect of the invention, there is provided a method of sorting demands with demand route segments in a ring, before loading the demands onto the ring, the method comprising the steps of:
a. sorting demands in order of decreasing containment, containment being the ratio of bandwidth-span distance product for the demand route""s spans in the ring to the bandwidth-span distance product for that part of the demand not yet loaded onto any ring;
b. sorting demands with equal containment in order of decreasing cycle involvement; and
c. sorting demands with equal containment and cycle involvement in order of decreasing number of demand route nodes in the ring.
According to a further aspect of the invention, there is provided a method of sorting demands with demand route segments in a ring, before loading the demands onto the ring, the method comprising the steps of:
ranking highest demands with demand routes fully contained in the ring;
sorting remaining demands in order of decreasing ratio of the number of the demand route""s spans in the ring to the total number of the demand route""s spans for that part of the demand not yet loaded on any ring;
sorting demands with the same ratio in b) in order of decreasing cycle involvement; and
sorting demands with the same ratio in b) and cycle involvement in order of decreasing number of demand route spans in the ring.
According to a further aspect of the invention, there is provided a method for selecting rings for implementation in a communications network, the communications network formed of plural spans connected by nodes for carrying data, the method comprising the steps of:
selecting a demand route for each demand , a demand being an amount of data required to be transmitted between a source node and a destination node and a demand route being a set of connected spans and nodes over which the demand is transmitted;
identifying a set of cycles, a cycle being a set of spans and their interconnecting nodes forming a closed path for travel once over each span and node in the cycle;
for each cycle in the set:
calculating the cost of carrying on the cycle the demands with demand route segments in the cycle, a demand route segment being any number of spans and nodes in a demand route; and
calculating a cost and performance value for the cycle; and
selecting cycles as rings to be implemented in the network based on the cost and performance values, and loading the demands onto the rings.
These and other aspects of the invention are described in the detailed description of the invention and claimed in the claims that follow.